// 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

// 二叉树的根是数组 nums 中的最大元素。
// 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
// 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
// 返回有给定数组 nums 构建的 最大二叉树 。

 

// 示例 1：
// 输入：nums = [3,2,1,6,0,5]
// 输出：[6,3,5,null,2,0,null,null,1]
// 解释：递归调用如下所示：
// - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//     - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//         - 空数组，无子节点。
//         - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//             - 空数组，无子节点。
//             - 只有一个元素，所以子节点是一个值为 1 的节点。
//     - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//         - 只有一个元素，所以子节点是一个值为 0 的节点。
//         - 空数组，无子节点。

  
// 示例 2：
// 输入：nums = [3,2,1]
// 输出：[3,null,2,null,1]
 

// 提示：
// 1 <= nums.length <= 1000
// 0 <= nums[i] <= 1000
// nums 中的所有整数 互不相同


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function (nums) {
  // 数组不为空就递归建树
  if (nums.length !== 0) {
      let
          // 最大值
          maxVal = Math.max.apply(null, nums),
          // 最大值的索引
          midIndex = nums.indexOf(maxVal),
          // 根据最大值创建的节点
          root = new TreeNode(maxVal);
      // 最大值值出现在数组首部，意味着以这个最大值为根节点的树没有左子树
      if (midIndex === 0) {
          root.left = null;
          root.right = constructMaximumBinaryTree(nums.slice(midIndex + 1))
      }
      // 最大值值出现在数组尾部，意味着以这个最大值为根节点的树没有右子树
      else if (midIndex === nums.length - 1) {
          root.left = constructMaximumBinaryTree(nums.slice(0, midIndex));
          root.right = null;
      }
      // 左右都有
      else {
          root.left = constructMaximumBinaryTree(nums.slice(0, midIndex));
          root.right = constructMaximumBinaryTree(nums.slice(midIndex + 1))
      }
      return root;
  }
  return null;
};